package org.algorithm.二师兄.数组.二月;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 四数之和 {


    public static void main(String[] args) {
        int[] arr = {1,0,-1,0,-2,2};
        int target = 0;
        List<List<Integer>> twoSum = fourSum(arr, target);
        System.out.println(Arrays.toString(twoSum.toArray()));
    }

    private static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){return res;}
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 0;i < len; i++){
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i+1; j < len; j++){
                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = len - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(left < right && sum > target){
                        right--;
                    }else if(left < right && sum < target){
                        left++;
                    }else{
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        // 去重
                        while(left < right && nums[left] == nums[++left]);
                        while(left < right && nums[right] == nums[--right]);
                    }
                }
            }
        }
        return res;
    }

}
